package main

import (
	"fmt"
	"maze/Queue"
	"os"
)

func readMaze(fileName string) [][]int {
	file, err := os.Open(fileName)
	defer file.Close()
	if err != nil {
		fmt.Printf("err: %s\n", err)
		return nil
	}
	var row, col int
	fmt.Fscanf(file, "%d %d\n", &row, &col)
	maze := make([][]int, row) // row 行 maze[]
	for i := range maze {
		maze[i] = make([]int, col) // maze[i] 有 col 列
		for j := range maze[i] {
			if j != col-1 {
				fmt.Fscanf(file, "%d", &maze[i][j])
			} else {
				fmt.Fscanf(file, "%d\n", &maze[i][j])
			}
		}
	}
	return maze
}

var dx = [4]int{0, 0, 1, -1}
var dy = [4]int{1, -1, 0, 0}

func main() {
	maze := readMaze("D:\\document\\Go\\src\\maze\\maze.in")
	//for _, row := range maze {
	//	for _, col := range row {
	//		fmt.Printf("%d ", col)
	//	}
	//	fmt.Println()
	//}
	n, m := len(maze), len(maze[0])
	dist := make([][]int, n)
	for i := range dist {
		dist[i] = make([]int, m)
	}
	queue := Queue.New()
	queue.Push(Queue.Node{0, 0})
	dist[0][0] = 1
	for !queue.Empty() {
		front := queue.Front()
		queue.Pop()
		x, y := front.X, front.Y
		fmt.Printf("%d %d\n", x, y)
		for i := 0; i < 4; i++ {
			a, b := x+dx[i], y+dy[i]
			if a < 0 || a >= n || b < 0 || b >= m {
				//fmt.Printf("1: %d %d\n", a, b)
				continue
			}
			if maze[a][b] == 0 {
				//fmt.Printf("2: %d %d\n", a, b)
				continue
			}
			if dist[a][b] != 0 {
				continue
			}
			dist[a][b] = dist[x][y] + 1
			queue.Push(Queue.Node{a, b})
		}
	}
	fmt.Println(dist[n-1][m-1] - 1)
}
